Tutorial Intro

TreeMap is a sorted implementation of the Map interface. It maintains its elements in a natural ordering (if they implement Comparable) or a custom comparator provided during creation. This ordering allows for efficient retrieval and navigation based on the key values.

Characteristics of TreeMap

✦Ordering: Elements in a TreeMap are always stored in a sorted order based on their keys. This is in contrast to HashMap, which is unordered. ✦Natural Ordering or Comparator: By default, TreeMap uses the elements' natural ordering (if they implement Comparable). You can optionally provide a custom Comparator during creation to define your own sorting logic. ✦Operations: TreeMap excels at operations that rely on the sorted nature of elements, such as finding the first or last key, retrieving elements within a specific range, or iterating through elements in sorted order. ✦Underlying Implementation: TreeMap typically uses a self-balancing binary search tree (like red-black tree) for efficient storage and retrieval of sorted elements.

Declaring and Initializing TreeMaps

Import syntax This line imports the TreeMap class from the java.util package.

Treemap import syntax import java.util.TreeMap;

Declaration

Declaration syntax TreeMap<KeyType, ValueType> myMap;

Explanation : This declares a variable named myMap of type TreeMap. The <KeyType> and <ValueType> placeholders specify the data types of the keys and values, respectively.

Initialization Default constructor This creates an empty TreeMap that uses the natural ordering of keys.

Creating empty treemap myMap = new TreeMap<KeyType, ValueType>();

Using a custom comparator This creates a TreeMap that uses the provided comparator for sorting keys.

Creating treemap with comparator Comparator<KeyType> myComparator = ...; // Define your custom comparator logic myMap = new TreeMap<KeyType, ValueType>(myComparator);

Important Methods in TreeMap

⮚firstKey(): Returns the first (smallest) key in the map according to the sorting order. ⮚lastKey(): Returns the last (largest) key in the map according to the sorting order. ⮚ceilingKey(key): Returns the least key in the map that is greater than or equal to the given key. ⮚floorKey(key): Returns the greatest key in the map that is less than or equal to the given key. ⮚subMap(fromKey, toKey): Returns a view of the portion of this map whose keys range from fromKey (inclusive) to toKey (exclusive). ⮚headMap(toKey): Returns a view of the portion of this map whose keys are less than toKey. ⮚tailMap(fromKey): Returns a view of the portion of this map whose keys are greater than or equal to fromKey.

Examples of TreeMap

1. Counting occurrences of words (String keys, Integer values):

Treemap example - counting words in sentence import java.util.*; public class Main { public static void main(String[] args) { String text = "This is the sample words to count the words"; TreeMap<String, Integer> wordCounts = new TreeMap<>(); for (String word : text.split(" ")) { word = word.toLowerCase(); // Case-insensitive counting int count = wordCounts.getOrDefault(word, 0); wordCounts.put(word, count + 1); } System.out.println("Word counts:"); for (Map.Entry<String, Integer> entry : wordCounts.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } } }

Output

Word counts: count: 1 is: 1 sample: 1 the: 2 this: 1 to: 1 words: 2

Explanation : This example uses TreeMap to store word counts. It iterates through the text, converting words to lowercase for case-insensitive counting. It uses getOrDefault to retrieve the existing count for a word (or 0 if not present) and increments it before putting it back in the map.

2. Storing student grades (Integer student IDs, Double grades):

Treemap example in java - student grade import java.util.Map; import java.util.TreeMap; public class Main { public static void main(String[] args) { Map<Integer, Double> grades = new TreeMap<>(); grades.put(123, 98.5); grades.put(456, 87.2); grades.put(789, 79.1); System.out.println("Student grades:"); for (Map.Entry<Integer, Double> entry : grades.entrySet()) { System.out.println("ID: " + entry.getKey() + ", Grade: " + entry.getValue()); } } }

Output

Student grades: ID: 123, Grade: 98.5 ID: 456, Grade: 87.2 ID: 789, Grade: 79.1

Explanation : This example demonstrates storing student IDs (integers) as keys and their corresponding grades (doubles) as values. It iterates through the map entries to print student IDs and grades.

3. Custom comparator for product inventory (String product names, Integer quantities):

Treemap example with comparator in java import java.util.*; public class Main { public static void main(String[] args) { Comparator<String> productNameComparator = new Comparator<String>() { @Override public int compare(String o1, String o2) { return o1.compareToIgnoreCase(o2); // Case-insensitive sorting } }; TreeMap<String, Integer> inventory = new TreeMap<>(productNameComparator); inventory.put("Laptop", 10); inventory.put("Mouse", 25); inventory.put("Keyboard", 15); inventory.put("Mouse", 10); inventory.put("Keyboard", 20); System.out.println("Product inventory:"); for (Map.Entry<String, Integer> entry : inventory.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } } }

Output

Product inventory: Keyboard: 20 Laptop: 10 Mouse: 10

Explanation : This example defines a custom comparator to sort product names (keys) case-insensitively. It then creates a TreeMap using this comparator and adds products with their quantities.

4. Navigable methods for finding specific entries (Character characters, String definitions):

Treemap example with navigable methods import java.util.*; public class Main { public static void main(String[] args) { TreeMap<Character, String> dictionary = new TreeMap<>(); dictionary.put('A', "Apple"); dictionary.put('B', "Banana"); dictionary.put('C', "Cat"); char keyToFind = 'B'; System.out.println("Definition for '" + keyToFind + "': " + dictionary.get(keyToFind)); System.out.println("Next word alphabetically: " + dictionary.higherEntry(keyToFind).getValue()); } }

Output

Definition for 'B': Banana Next word alphabetically: Cat

Explanation : This example utilizes the TreeMap's navigable methods. It retrieves the definition for a specific character key and then finds the next word alphabetically using higherEntry.

Tutorials